package com.tgy.algorithm.base;

import java.util.Stack;

/**
 *  1 2 3 3 2 1
 */
public class _单链表判断是否是回文_01 {

    public static Node generalNode(int[] nums) {
        if (nums == null || nums.length == 0) {
            return null;
        }
        Node header = new Node(nums[0], null);
        Node cur = header;
        for (int i = 1; i < nums.length; i++) {
            Node node = new Node(nums[i], null);
            cur.next = node;
            cur = node;
        }

        return header;
    }

    public static void printNode(Node header) {
        while (header != null) {
            System.out.print(header.num + ", ");
            header = header.next;
        }
        System.out.println();
    }

    public static boolean isPalindrome01(Node header) {

        Stack<Integer> integers = new Stack<>();
        Node cur = header;
        while (cur != null) {
            integers.push(cur.num);
            cur = cur.next;
        }

        cur = header;
        while (!integers.isEmpty()) {
            Integer pop = integers.pop();
            if (cur.num != pop) {
                return false;
            }
            cur = cur.next;
        }

        return true;
    }

    public static boolean isPalindrome02(Node header) {

        if (header == null) {
            return false;
        }

        if (header.next == null) {
            return true;
        }

        Node slow = header;
        // 这里使用header在fast到最后到时候，slow正好到达终点，如果是偶数个节点，则到达中间元素的下一个节点
        Node fast = header;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

//        System.out.println(slow.num + " " +slow.next.num);
        Stack<Integer> integers = new Stack<>();
        // 把后半部分写入到栈中
        while (slow != null) {
            integers.push(slow.num);
            slow = slow.next;
        }
        while (!integers.isEmpty()) {
            if (integers.pop() != header.num) {
                return false;
            }
            header = header.next;
        }

        return true;
    }

    public static boolean isPalindrome03(Node header) {
        if (header == null){
            return false;
        }

        if (header.next == null) {
            return true;
        }

        Node slow = header;
        Node fast = header.next;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        Node pre = null;
        Node cur = slow.next;
        Node next = null;
        while (cur != null) {
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        Node tmpNode = pre;
        cur = header;
        boolean flag = true;
        while (pre != null) {
            if (cur.num != pre.num) {
                flag = false;
                break;
            }
            cur = cur.next;
            pre = pre.next;
        }

        // 恢复链表
        pre = null;
        cur = tmpNode;
        while (cur != null) {
           next = cur.next;
           cur.next = pre;
           pre = cur;
           cur = next;
        }

        return flag;
    }

    public static void main(String[] args) {
        int[] nums = {1,2,2,1};
//        int[] nums = {1,2,3,2,1};
        Node node = generalNode(nums);
//        printNode(node);
        boolean palindrome01 = isPalindrome03(node);
        System.out.println(palindrome01);
        printNode(node);
    }
}
